The present invention relates to performing calculations, such as conditional carry addition, incrementation, and priority encoding, on a monolithic integrated circuit. The invention allows for the manufacture of relatively non-complex integrated circuits, wherein calculations can be made using a binary tree, so that the number of logic stages necessary to perform each calculation is proportional to log.sub.2 times the number of bits on which the calculation is performed.
Design of optimal large scale integrated circuits requires a minimization of chip complexity for ease of production, and a maximization of speed with which the circuit can perform a calculation. Complexity can be reduced by dividing a circuit into cells, wherein each cell performs part of a calculation, and each cell is identical or substantially similar to other cells on the circuit. Speed can be increased by reducing the number of logic stages necessary to perform a calculation, thereby reducing the delay it takes to perform a calculation.
FIG. 1 shows a prior art ripple adder cell. A.sub.i and B.sub.i are individual i.sub.th order bits of the two operands to be added. C.sub.i (in) is the carry-in signal from the prior adder cell, C.sub.i (out) is the carry-out signal from the present cell, and Sum.sub.i is the sum signal of the present cell. The carry-out signal of one cell is the carry-in signal to the next cell. Using Boolean logic, where "+" is the Boolean "OR", "*" is the Boolean "AND", and "XOR" is the Boolean "exclusive-OR": the logic could be expressed as: EQU Sum.sub.i =(A.sub.i XOR B.sub.i) XOR C.sub.i (in) EQU C.sub.i (out)=((A.sub.i +B.sub.i)*C.sub.i (in))+(A.sub.i *B.sub.i)
FIG. 2 shows how a full ripple adder, for adding two binary numbers, can be formed by connecting any number of ripple adder cells in series. This can be done by connecting C.sub.i (out) to C.sub.i+1 (in) for every ripple cell, 1 to n, where 1 is the least significant bit and n is the most significant bit of the binary addition.
The ripple adder can be implemented on a large scale integrated circuit with low chip complexity, because every ripple adder cell is exactly the same. The number of logic stages necessary for performing a calculation, however, is directly proportional to the number of bits, as each cell of the ripple adder performs one logic stage of the addition, and the calculation within each cell cannot be performed until the output of very prior cell is determined. This makes the ripple adder relatively slow.
Other prior art schemes have been able to increase the speed of addition and other calculations using such techniques as carry lookahead or other conditional carry techniques. At least one prior art scheme has provided a scheme wherein the number of logic stages necessary to perform each calculation is proportional to log.sub.2 times the number of bits on which the calculation is performed. (See copending patent application Ser. No. 410,807, Frederick A. Ware, "Conditional Carry Techniques For Digital Processors", filed Aug. 23, 1982; however no prior art has allowed for the production of circuits where the number of logic stages necessary to perform each calculation is proportional to log.sub.2 times the number of bits on which the calculation is performed, and the circuit may be layed out in a non-complex fashion.